# @algorithm @lc id=2103 lang=python3 weekname=biweekly-contest-60
# @title find-all-groups-of-farmland


from cn.Python3.mod.preImport import *
# @test([[1,0,0],[0,1,1],[0,1,1]])=[[0,0,0,0],[1,1,2,2]]
# @test([[1,1],[1,1]])=[[0,0,1,1]]
# @test([[0]])=[]
class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        import collections
        store = collections.deque()
        m, n = len(land), len(land[0])
        visit = [[False]*n for _ in range(m)]
        ans = []
        for i in range(m):
            for j in range(n):
                if visit[i][j] or not land[i][j]:
                    continue
                tmpAns = [i, j, i, j]
                visit[i][j]=True
                store.append([i, j])
                while store:
                    x, y = store.popleft()
                    for tmpDir in directions:
                        newX, newY = x+tmpDir[0], y+tmpDir[1]
                        if 0<=newX<m and 0<=newY<n and land[newX][newY] and not visit[newX][newY]:
                            store.append([newX, newY])
                            visit[newX][newY]=True
                            if newX<=tmpAns[0] and newY<=tmpAns[1]:
                                tmpAns[0] = newX
                                tmpAns[1] = newY
                            if newX>=tmpAns[2] and newY>=tmpAns[3]:
                                tmpAns[2] = newX
                                tmpAns[3] = newY
                ans.append(tmpAns)
        return ans